package leetcode.秋招.五八;

/**
 * @author ：zsy
 * @date ：Created 2021/9/25 19:25
 * @description：
 */
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 写出返回最小砝码所需数量的实现代码
     * @param weights int整型一维数组 输入任意砝码数组
     * @param total int整型 目标值
     * @return int整型
     */
    public int weight (int[] weights, int total) {
        // write code here
        if (total == 0) return 0;
        int min = Integer.MAX_VALUE;
        int[] dp = new int[total + 1];
        for (int weight : weights) {
            min = Math.min(min, weight);
        }
        if (min > total) return -1;
        for (int i = 1; i < total + 1; i++) {
            dp[i] = total + 1;
            for (int weight : weights) {
                if (i - weight < 0) continue;
                dp[i] = Math.min(dp[i], 1 + dp[i - weight]);
            }
        }
        return dp[total] == total + 1 ? -1 : dp[total];
    }
}
